/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/zigzag-iterator-ii
   @Language: C++
   @Datetime: 19-05-06 13:52
   */

class ZigzagIterator2 {
	vector<vector<int> > *vecs;
	vector<int> cols;
	int row;
public:
	/*
	 * @param vecs: a list of 1d vectors
	 */ZigzagIterator2(vector<vector<int> > &vecs) {
		 // do intialization if necessary
		 this->vecs=&vecs;
		 cols.assign(vecs.size(),0);
		 row=0;
	 }

	 /*
	  * @return: An integer
	  */
	 int next() {
		 // write your code here
		 int a = (*vecs)[row][cols[row]];
		 cols[row++]++;
		 return a;
	 }

	 /*
	  * @return: True if has next
	  */
	 bool hasNext() {
		 // write your code here
		 for(int i=row; i<cols.size()+row; ++i){
			 const int id=i%cols.size();
			 if(cols[id]<(*vecs)[id].size()) {
				 row=id;
				 return true;
			 }
		 }
		 return false;
	 }
};

/**
 * Your ZigzagIterator2 object will be instantiated and called as such:
 * ZigzagIterator2 solution(vecs);
 * while (solution.hasNext()) result.push_back(solution.next());
 * Ouptut result
 */
